package cn.fxzhang.leetcode.no03;

/**
 * 363. 矩形区域不超过 K 的最大数值和
 * 你一个 m x n 的矩阵 matrix 和一个整数 k ，找出并返回矩阵内部矩形区域的不超过 k 的最大数值和。
 * 题目数据保证总会存在一个数值和不超过 k 的矩形区域。
 * m == matrix.length
 * n == matrix[i].length
 * 1 <= m, n <= 100
 * -100 <= matrix[i][j] <= 100
 * -10^5 <= k <= 10^5
 *
 * 类型：枚举
 * 题解：枚举起点和终点
 * 时间复杂度：O(N^2*M^2)
 * 空间复杂度：O(N*M)
 *
 * 提交记录(1/1)：
 * 执行用时: 325 ms, 击败了28.89%
 * 内存消耗: 38.7 MB, 击败了54.09%
 * todo O(NlogN * M^2)的解法
 * @author 张晓帆
 * @date 2021/4/22
 */
public class P0363_Max_Sum_Of_Rectangle_No_Larger_Than_K {

    public int maxSumSubmatrix(int[][] matrix, int k) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] sum = new int[m+1][n+1];

        for (int i=1; i<=m; i++){
            for (int j=1; j<=n; j++){
                sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+matrix[i-1][j-1];
            }
        }

        int max = Integer.MIN_VALUE;
        for (int i=1; i<=m; i++){
            for (int j=1; j<=n; j++){
                for (int x=i; x<=m; x++){
                    for (int y=j; y<=n; y++){
                        int tmp = sum[x][y]-sum[i-1][y]-sum[x][j-1]+sum[i-1][j-1];
                        if (tmp<=k && tmp>max){
                            max = tmp;
                        }
                    }
                }
            }
        }
        return max;
    }
}
